package com.liuwei.spring.cloud.junit.leetcode.interview;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class ClimbStairs {

    /**
     * https://leetcode.cn/problems/climbing-stairs/
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * @param args
     */
    public static void main(String[] args) {
        int stairs = 5;
    }

    int climbStairs(int n) {
        int total = 0;
        for (int i = 0; i <= n/2; i++) {
            BigInteger amount = Cn(n,i);
            total = total + amount.intValue();
        }
        return total;
    }

    public static BigInteger Cn(int total,int m){
        if (m == total || m == 0) return BigInteger.ONE;
        return factorial(total).divide(factorial(total-m)).divide(factorial(m));
    }

    public static BigInteger factorial(int n) {
        // 限制递归的堆栈深度为 100, 防止递归深度异常
        for (int i = 1; i <= n ; i= i+100) {
            cache.put(String.valueOf(i),factorial(cache,i));
        }
        return factorial(cache,n);
    }

    private static Map<String,BigInteger> cache = new HashMap<>();
    private static BigInteger factorial(Map<String,BigInteger> cache,int n){
        if(cache.containsKey(String.valueOf(n))){
            return cache.get(String.valueOf(n));
        }
        if (n <= 1) {
            cache.put(String.valueOf(n),BigInteger.ONE);
            return BigInteger.ONE;
        }
        BigInteger result = BigInteger.valueOf(n).multiply(factorial(cache,n-1));
        cache.put(String.valueOf(n),result);
        return result;
    }
}
